МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ІКНІТ
Методичні вказівки до лабораторної роботи № 5,6
"Транспортна задача. Метод потенціалів "
з дисципліни
“Математичні методи дослідження операцій”
для студентів спеціальності 6.08.04 “Комп’ютерні науки”
Львів – 2002
Методичні вказівки до лабораторної роботи № 5,6 “Транспортна задача. Метод потенціалів" з дисципліни “Математичні методи дослідження операцій” для студентів спеціальності 6.08.04 “Комп’ютерні науки” /Укл. Дронюк І.М. – Львів: Національний університет «Львівська політехніка», 2002.
Укладач: Дронюк І.М., канд. фіз.-мат. наук, доц..
Відповідальний за випуск: Обельовська К.М., канд. техн. наук, доц.
Рецензент: Різник В.В., докт. техн. наук, проф.
Лабораторна робота № 5
Тема: Транспортна задача. Метод потенціалів
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel
Порядок роботи:
Заповнити початкову таблицю транспортної задачі лінійного програмування згідно заданого варіанту.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям методу потенціалів задачі лінійного програмування.
Знайти мінімальне значення цільової функції та оптимальний розв'язок.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком
назва роботи
мета роботи
порядок роботи
короткі теоретичні відомості
алгоритм розв'язку задачі
малюнки відповідних таблиць
аналіз отриманих результатів та висновки
Короткі теоретичні відомості
Постановка
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1 i m, 1 j n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Розв’язування
Умови Т-задачі записуються у вигляді
ai
С = EMBED Equation.3 EMBED Equation.3
bj b1 b2 b3 … bn
Введемо змінні хij 0, 1 i m, 1 j n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва в пункт споживання j.
Необхідно знайти множину значень змінних хij 0, мінімізуючи функцію
L = EMBED Equation.3 ,
з виконанням умов
EMBED Equation.3
Матрицю
Х = EMBED Equation.3
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута».
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута.
Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай + = t + 2. Знаходимо x = min{ EMBED Equation.3 }, де
EMBED Equation.3 .
Якщо EMBED Equation.3 , то заповнюється -ий рядок матриці, починаючи з (+1)-го елемента, нулями. Якщо EMBED Equation.3 , то заповнюється нулями -й стовбець, починаючи з (...
